#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

typedef struct sQueueNode *PtrToQueueNode;
struct sQueueNode {
    double data;
    PtrToQueueNode next;
};  //这是队列中的节点
typedef PtrToQueueNode QueueNode;

typedef struct sQueue *PtrToQueue;
struct sQueue {
    QueueNode front, rear;   //队列头尾指针
    int max_size;            //队列最大容量
};  //这是队列
typedef PtrToQueue Queue;

Queue CreateQueue(int);
bool InsertElem(Queue, double);
bool IsEmpty(Queue);
void DisplayElem(Queue);
bool DeleteElem(Queue);

int main()
{
    int max_size = 8;
    Queue Q = CreateQueue(max_size);

    InsertElem(Q, 1.5);             //表尾
    InsertElem(Q, 15.58);
    InsertElem(Q, 551.55);
    InsertElem(Q, 5412.05);         //表头
    DisplayElem(Q);

    if(DeleteElem(Q))
        printf("Delete Success !\n");

    DisplayElem(Q);

    printf("zxc%lf ", Q->rear->data);  //表尾
    printf("zxc%lf ", Q->front->data); //表头
    if (Q->rear->next == NULL)
        printf("Right NULL !");
    Sleep(5000);

    return 0;
}


/*
创建队列
1. front指向链表的头结点，rear指向尾结点，在尾部插入结点，在头部删除结点
2. 在创建队列时，front和rear都指向NULL
3. 插入结点时，更新rear
4. 删除结点时，更新front
*/
Queue CreateQueue(int max_size)
{
    Queue Q = (Queue)malloc(sizeof(struct sQueue));
    Q->front = NULL;
    Q->rear = NULL;
    Q->max_size = max_size;

    return Q;
}


/*
判断空队列
1. 如果头指针指向NULL，则队列为空
2. 那么尾指针指向NULL，队列是否为空
*/
bool IsEmpty(Queue Q)
{
    return (Q->front == NULL);
}


/*
插入队列节点
1. 分配新节点内存，并设置节点值，将新节点指向NULL
2. 队列为空时，则队列的头尾指针都要指向新节点
3. 队列不为空时，则在尾部插入新节点，具体操作为：尾结点指向新结点，尾指针指向新节点
*/
bool InsertElem(Queue Q, double insert_number)
{
    QueueNode new_queue_node;

    new_queue_node = (QueueNode)malloc(sizeof(struct sQueueNode));
    new_queue_node->data = insert_number;
    new_queue_node->next = NULL;

    if(IsEmpty(Q))
    {
        Q->rear = new_queue_node;
        Q->front = new_queue_node;
        Q->rear->next = NULL;
    }
    else
    {
        Q->rear->next = new_queue_node;
        Q->rear = new_queue_node;
    }
    
    return true;
}


/*
删除队列节点
1. 检查队列是否为空
2. 建立临时结点指向头结点
3. 若队列中只有一个结点，则头尾指针指向NULL
4. 一般情况下，头指针指向头结点的前一个结点
5. 释放原头结点内存
*/
bool DeleteElem(Queue Q)
{
    if(IsEmpty(Q))
    {
        printf("Queue is empty !\n");
        return false;
    }

    QueueNode tmp;
    tmp = Q->front;
    if(Q->front == Q->rear)
        Q->front = Q->rear = NULL;
    else    
        Q->front = tmp->next;
    free(tmp);

    return true;
}


/*
打印队列
*/
void DisplayElem(Queue Q)
{
    QueueNode tmp;
    printf("\n");
    for (tmp = Q->front; tmp != NULL; tmp = tmp->next)
        printf("%lf ", tmp->data);
    printf("\n\n");
}